package BinarySearch;

public class binarySearch {
    /*
    数组中找第一个与key相同的元素
     */
    int searchFirstEqual(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left < arr.length && arr[left] == key) return left;
        return -1;
    }

    /*
    数组中找最后一个与key相同的元素
     */
    int searchLastEqual(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (right >= 0 && arr[right] == key) return right;
        return -1;
    }


    /*
    找第一个 大于等于key 的位置
     */
    int searchFirstEqualOrLarger(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left >= arr.length) return -1;
        return left;
    }

    /*
    找第一个 大于key 的位置
     */
    int searchFirstLarger(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left >= arr.length) return -1;
        return left;
    }

    /*
    找最后一个等于或者小于key的元素
     */
    int searchLastEqualOrSmaller(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // if (right == -1) return -1;
        return right;
    }

    /*
    找最后一个小于key的元素
     */
    int searchLastSmaller(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= key) right = mid - 1;
            else if (arr[mid] < key) left = mid + 1;
        }
        // if (right == -1) return -1;
        return right;
    }

}
